home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Unix / Shells / zsh / Source / src / mem.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-07  |  21.6 KB  |  1,031 lines
  1. /*
  2.  *
  3.  * mem.c - memory management
  4.  *
  5.  * This file is part of zsh, the Z shell.
  6.  *
  7.  * This software is Copyright 1992 by Paul Falstad
  8.  *
  9.  * Permission is hereby granted to copy, reproduce, redistribute or otherwise
  10.  * use this software as long as: there is no monetary profit gained
  11.  * specifically from the use or reproduction of this software, it is not
  12.  * sold, rented, traded or otherwise marketed, and this copyright notice is
  13.  * included prominently in any copy made.
  14.  *
  15.  * The author make no claims as to the fitness or correctness of this software
  16.  * for any use whatsoever, and it is provided as is. Any use of this software
  17.  * is at the user's own risk.
  18.  *
  19.  */
  20.  
  21. #include "zsh.h"
  22.  
  23. vptr(*alloc) DCLPROTO((int));
  24. vptr(*ncalloc) DCLPROTO((int));
  25.  
  26.  
  27. /*
  28.  
  29.     There are two ways to allocate memory in zsh.  The first way is
  30.     to call zalloc/zcalloc, which call malloc/calloc directly.  It
  31.     is legal to call realloc() or free() on memory allocated this way.
  32.     The second way is to call halloc/hcalloc, which allocates memory
  33.     from one of the memory pools on the heap stack.  A pool can be
  34.     created by calling pushheap(), and destroyed by calling popheap().
  35.     To free the memory in the pool without destroying it, call
  36.     freeheap(); this is equivalent to { popheap(); pushheap(); }
  37.     Memory allocated in this way does not have to be freed explicitly;
  38.     it will all be freed when the pool is destroyed.  In fact,
  39.     attempting to free this memory may result in a core dump.
  40.     The pair of pointers ncalloc and alloc may point to either
  41.     zalloc & zcalloc or halloc & hcalloc; permalloc() sets them to the
  42.     former, and heapalloc() sets them to the latter. This can be useful.
  43.     For example, the dupstruct() routine duplicates a syntax tree,
  44.     allocating the new memory for the tree using alloc().  If you want
  45.     to duplicate a structure for a one-time use (i.e. to execute the list
  46.     in a for loop), call heapalloc(), then dupstruct().  If you want
  47.     to duplicate a structure in order to preserve it (i.e. a function
  48.     definition), call permalloc(), then dupstruct().
  49.  
  50.     If we use zsh's own allocator we use a simple trick to avoid that
  51.     the (*real*) heap fills up with empty zsh-heaps: we allocate a
  52.     large block of memory before allocating a heap pool, this memory
  53.     is freed again immediatly after the pool is allocated. If there
  54.     are only small blocks on the free list this guarentees that the
  55.     memory for the pool is at the end of the memory which means that
  56.     we can give it back to the systems when the pool is freed.
  57. */
  58.  
  59. #if defined(MEM_DEBUG) && defined(USE_ZSH_MALLOC)
  60.  
  61. int h_m[1025], h_push, h_pop, h_free;
  62.  
  63. #endif
  64.  
  65.  
  66. #define H_ISIZE  sizeof(long)
  67.  
  68. #define HEAPSIZE (8192 - H_ISIZE)
  69. #define HEAPFREE (16384 - H_ISIZE)
  70.  
  71. /* set default allocation to heap stack */
  72.  
  73. void heapalloc()
  74. {                /**/
  75.     alloc = hcalloc;
  76.     ncalloc = halloc;
  77.     useheap = 1;
  78. }
  79.  
  80. static vptr(*lastcalloc) DCLPROTO((int));
  81. static vptr(*lastncalloc) DCLPROTO((int));
  82. static int lastuseheap;
  83.  
  84. /* set default allocation to malloc() */
  85.  
  86. void permalloc()
  87. {                /**/
  88.     lastcalloc = alloc;
  89.     lastncalloc = ncalloc;
  90.     lastuseheap = useheap;
  91.     alloc = zcalloc;
  92.     ncalloc = zalloc;
  93.     useheap = 0;
  94. }
  95.  
  96. /* reset previous default allocation */
  97.  
  98. void lastalloc()
  99. {                /**/
  100.     alloc = lastcalloc;
  101.     ncalloc = lastncalloc;
  102.     useheap = lastuseheap;
  103. }
  104.  
  105. struct heappos {
  106.     struct heappos *next;
  107.     char *ptr;
  108.     int free;
  109. };
  110.  
  111. struct heap {
  112.     struct heap *next;
  113.     struct heappos pos;
  114.     char *arena;
  115. };
  116.  
  117. Heap heaps;
  118.  
  119. /* create a memory pool */
  120.  
  121. void pushheap()
  122. {                /**/
  123.     Heap h;
  124.     Heappos hp;
  125.  
  126. #if defined(MEM_DEBUG) && defined(USE_ZSH_MALLOC)
  127.     h_push++;
  128. #endif
  129.  
  130.     for (h = heaps; h; h = h->next) {
  131.     hp = (Heappos) zalloc(sizeof(*hp));
  132.     hp->next = h->pos.next;
  133.     h->pos.next = hp;
  134.     hp->free = h->pos.free;
  135.     hp->ptr = h->pos.ptr;
  136.     }
  137. }
  138.  
  139. /* reset a memory pool */
  140.  
  141. void freeheap()
  142. {                /**/
  143.     Heap h;
  144.  
  145. #if defined(MEM_DEBUG) && defined(USE_ZSH_MALLOC)
  146.     h_free++;
  147. #endif
  148.     for (h = heaps; h; h = h->next) {
  149.     if (h->pos.next) {
  150.         h->pos.free = h->pos.next->free;
  151.         h->pos.ptr = h->pos.next->ptr;
  152.     }
  153.     else {
  154.         h->pos.free += (int)(h->pos.ptr - h->arena);
  155.         h->pos.ptr = h->arena;
  156.     }
  157.     }
  158. }
  159.  
  160. /* destroy a memory pool */
  161.  
  162. void popheap()
  163. {                /**/
  164.     Heap h, hn, hl = NULL;
  165.     Heappos hp, hpn;
  166.  
  167. #if defined(MEM_DEBUG) && defined(USE_ZSH_MALLOC)
  168.     h_pop++;
  169. #endif
  170.  
  171.     for (h = heaps; h; h = hn) {
  172.     hn = h->next;
  173.     if ((hp = h->pos.next)) {
  174.         h->pos.next = hp->next;
  175.         h->pos.free = hp->free;
  176.         h->pos.ptr = hp->ptr;
  177.         zfree(hp, sizeof(struct heappos));
  178.         hl = h;
  179.     }
  180.     else {
  181.         for (hp = h->pos.next; hp; hp = hpn) {
  182.         hpn = hp->next;
  183.         free(hp);
  184.         }
  185.         zfree(h->arena, HEAPSIZE);
  186.         zfree(h, sizeof(struct heap));
  187.     }
  188.     }
  189.     if (hl)
  190.     hl->next = NULL;
  191.     else
  192.     heaps = NULL;
  193. }
  194.  
  195. /* allocate memory from the current memory pool */
  196.  
  197. vptr halloc(size)        /**/
  198. int size;
  199. {
  200.     Heap h, hp;
  201.     char *ret;
  202.  
  203.     zigunsafe();
  204.  
  205.     size = (size + H_ISIZE - 1) & ~(H_ISIZE - 1);
  206.  
  207. #if defined(MEM_DEBUG) && defined(USE_ZSH_MALLOC)
  208.     h_m[size < 1024 ? (size / H_ISIZE) : 1024]++;
  209. #endif
  210.  
  211.     for (h = heaps; h && h->pos.free < size; h = h->next);
  212.  
  213.     if (h) {
  214.     ret = h->pos.ptr;
  215.     h->pos.ptr += size;
  216.     h->pos.free -= size;
  217.     }
  218.     else {
  219.     int n = (size > HEAPSIZE) ? size : HEAPSIZE;
  220.  
  221. #ifdef USE_ZSH_MALLOC
  222.     static int called = 0;
  223.     vptr foo;
  224.  
  225.     if (called)
  226.         foo = (vptr) malloc(HEAPFREE);
  227. #endif
  228.  
  229.     for (hp = NULL, h = heaps; h; hp = h, h = h->next);
  230.  
  231.     h = (Heap) zalloc(sizeof *h);
  232.     h->arena = (char *) zalloc(n);
  233.  
  234. #ifdef USE_ZSH_MALLOC
  235.     if (called)
  236.         zfree(foo, HEAPFREE);
  237.     called = 1;
  238. #endif
  239.  
  240.     h->next = NULL;
  241.  
  242.     if (hp)
  243.         hp->next = h;
  244.     else
  245.         heaps = h;
  246.  
  247.     h->pos.next = NULL;
  248.     h->pos.ptr = h->arena + size;
  249.  
  250.     h->pos.free = n - size;
  251.  
  252.     ret = h->arena;
  253.     }
  254.  
  255.     zigsafe();
  256.  
  257.     return (vptr) ret;
  258. }
  259.  
  260. /* allocate memory from the current memory pool and clear it */
  261.  
  262. vptr hcalloc(size)        /**/
  263. int size;
  264. {
  265.     vptr ptr;
  266.  
  267.     ptr = halloc(size);
  268.     memset(ptr, 0, size);
  269.     return ptr;
  270. }
  271.  
  272. vptr hrealloc(p, old, new)    /**/
  273. char *p;
  274. int old;
  275. int new;
  276. {
  277.     char *ptr;
  278.  
  279.     ptr = (char *)halloc(new);
  280.     memcpy(ptr, p, old);
  281.     return (vptr) ptr;
  282. }
  283.  
  284. /* allocate permanent memory */
  285.  
  286. vptr zalloc(l)            /**/
  287. int l;
  288. {
  289.     vptr z;
  290.  
  291.     zigunsafe();
  292.  
  293.     if (!l)
  294.     l = 1;
  295.     if (!(z = (vptr) malloc(l))) {
  296.     zerr("fatal error: out of memory", NULL, 0);
  297.     exit(1);
  298.     }
  299.     
  300.     zigsafe();
  301.  
  302.     return z;
  303. }
  304.  
  305. vptr zcalloc(size)        /**/
  306. int size;
  307. {
  308.     vptr ptr;
  309.  
  310.     ptr = zalloc(size);
  311.     memset(ptr, 0, size);
  312.     return ptr;
  313. }
  314.  
  315. char *dupstring(s)        /**/
  316. const char *s;
  317. {
  318.     char *t;
  319.  
  320.     if (!s)
  321.     return NULL;
  322.     t = (char *)ncalloc(strlen((char *)s) + 1);
  323.     strcpy(t, s);
  324.     return t;
  325. }
  326.  
  327. char *ztrdup(s)            /**/
  328. const char *s;
  329. {
  330.     char *t;
  331.  
  332.     if (!s)
  333.     return NULL;
  334.     t = (char *)zalloc(strlen((char *)s) + 1);
  335.     strcpy(t, s);
  336.     return t;
  337. }
  338.  
  339.  
  340. #ifdef USE_ZSH_MALLOC
  341.  
  342. /*
  343.    Below is a simple segment oriented memory allocator for systems on 
  344.    which it is better than the system's one. Memory id given in blocks
  345.    aligned to an integer multiple of sizeof(long) (4 bytes on most machines, 
  346.    but 8 bytes on e.g. a dec alpha). Each block is preceded by a header
  347.    which contains the length of the data part (in bytes). In allocated 
  348.    blocks only this field of the structure m_hdr is senseful. In free
  349.    blocks the second field (next) is a pointer to the next free segment
  350.    on the free list.
  351.  
  352.    On top of this simple allocator there is a second allocator for small
  353.    chunks of data. It should be both faster and less space-consuming than
  354.    using the normal segment mechanism for such blocks.
  355.    For the first M_NSMALL-1 possible sizes memory is allocated in arrays
  356.    that can hold M_SNUM blocks. Each array is stored in one segment of the
  357.    main allocator. In these segments the third field of the header structure
  358.    (free) contains a pointer to the first free block in the array. The
  359.    last field (used) gives the number of already used blocks in the array.
  360.  
  361.    If the macro name MEM_DEBUG is defined, some information about the memory 
  362.    usage is stored. This information can than be viewed by calling the
  363.    builtin `mem' (which is only available if MEM_DEBUG is set).
  364.  
  365.    If MEM_WARNING is defined, error messages are printed in case of errors.
  366.  
  367.    If SECURE_FREE is defined, free() checks if the given address is really
  368.    one that was returned by malloc(), it ignores it if it wasn't (printing
  369.    an error message if MEM_WARNING is also defined).
  370. */
  371. #if !defined(__hpux) && !defined(DGUX)
  372. #if defined(_BSD) && !defined(SYSV)
  373.  
  374. extern int brk DCLPROTO((caddr_t));
  375. extern caddr_t sbrk DCLPROTO((int));
  376.  
  377. #else
  378.  
  379. extern int brk DCLPROTO((void *));
  380. extern void *sbrk DCLPROTO((int));
  381.  
  382. #endif
  383. #endif
  384.  
  385. #if defined(_BSD) && !defined(HAS_STDLIB)
  386.  
  387. #define FREE_RET_T int
  388. #define FREE_ARG_T char *
  389. #define FREE_DO_RET
  390. #define MALLOC_RET_T char *
  391. #define MALLOC_ARG_T size_t
  392.  
  393. #else
  394.  
  395. #define FREE_RET_T void
  396. #define FREE_ARG_T void *
  397. #define MALLOC_RET_T void *
  398. #define MALLOC_ARG_T size_t
  399.  
  400. #endif
  401.  
  402. struct m_shdr {
  403.     struct m_shdr *next;
  404. };
  405.  
  406. struct m_hdr {
  407.     long len;
  408.     struct m_hdr *next;
  409.     struct m_shdr *free;
  410.     long used;
  411. };
  412.  
  413.  
  414. #define M_ALIGN (sizeof(long))
  415.  
  416. #define M_HSIZE (sizeof(struct m_hdr))
  417. #define M_ISIZE (sizeof(long))
  418. #define M_MIN   (2 * M_ISIZE)
  419.  
  420. struct m_hdr *m_lfree, *m_free;
  421. long m_pgsz = 0;
  422. char *m_high, *m_low;
  423.  
  424.  
  425. #define M_SIDX(S)  ((S) / M_ISIZE)
  426. #define M_SNUM     50
  427. #define M_SLEN(M)  ((M)->len / M_SNUM)
  428. #define M_SBLEN(S) ((S) * M_SNUM + sizeof(struct m_shdr *) +  \
  429.             sizeof(long) + sizeof(struct m_hdr *))
  430. #define M_BSLEN(S) (((S) - sizeof(struct m_shdr *) -  \
  431.              sizeof(long) - sizeof(struct m_hdr *)) / M_SNUM)
  432. #define M_NSMALL 8
  433.  
  434.  
  435. struct m_hdr *m_small[M_NSMALL];
  436.  
  437.  
  438.  
  439. #ifdef MEM_DEBUG
  440.  
  441. int m_s = 0, m_b = 0;
  442. int m_m[1025], m_f[1025];
  443.  
  444. struct m_hdr *m_l;
  445.  
  446. #endif
  447.  
  448. MALLOC_RET_T malloc(size)
  449. MALLOC_ARG_T size;
  450. {
  451.     struct m_hdr *m, *mp, *mt;
  452.     long n, s, os;
  453.     struct heap *h, *hp, *hf = NULL, *hfp;
  454.  
  455.     if (!size)
  456.     return (MALLOC_RET_T) m_high;
  457.  
  458.     if (!m_pgsz) {
  459. #ifdef __hpux
  460.     extern long sysconf DCLPROTO((int));
  461.  
  462.     m_pgsz = sysconf(_SC_PAGE_SIZE);
  463. #else
  464. #ifdef SYSV
  465.     extern long sysconf DCLPROTO((int));
  466.  
  467.     m_pgsz = sysconf(_SC_PAGESIZE);
  468. #else
  469.     extern int getpagesize DCLPROTO((void));
  470.  
  471.     m_pgsz = getpagesize();
  472. #endif
  473. #endif
  474.     m_free = m_lfree = NULL;
  475.     }
  476.  
  477.     size = (size + M_ALIGN - 1) & ~(M_ALIGN - 1);
  478.  
  479.     if ((s = M_SIDX(size)) && s < M_NSMALL) {
  480.     for (mp = NULL, m = m_small[s]; m && !m->free; mp = m, m = m->next);
  481.  
  482.     if (m) {
  483.         struct m_shdr *sh = m->free;
  484.  
  485.         m->free = sh->next;
  486.         m->used++;
  487.  
  488.         if (m->used == M_SNUM && m->next) {
  489.         for (mt = m; mt->next; mt = mt->next);
  490.         
  491.         mt->next = m;
  492.         if (mp)
  493.             mp->next = m->next;
  494.         else
  495.             m_small[s] = m->next;
  496.         m->next = NULL;
  497.         }
  498.  
  499. #ifdef MEM_DEBUG
  500.         m_m[size / M_ISIZE]++;
  501. #endif
  502.  
  503.         return (MALLOC_RET_T) sh;
  504.     }
  505.  
  506.     os = size;
  507.     size = M_SBLEN(size);
  508.     }
  509.     else
  510.     s = 0;
  511.  
  512.     for (mp = NULL, m = m_free; m && m->len < size; mp = m, m = m->next);
  513.  
  514.     /* If there is an empty zsh heap at a lower address we steel it and take
  515.        the memory from it, putting the rest on the free list. */
  516.     
  517.     for (hp = NULL, h = heaps; h; hp = h, h = h->next)
  518.     if (h->pos.ptr == h->arena &&
  519.         (!hf || h < hf) &&
  520.         (!m || ((char *) m) > ((char *) h)))
  521.         hf = h, hfp = hp;
  522.  
  523.     if (hf) {
  524.     struct heappos *hpo, *hpn;
  525.  
  526.     for (hpo = hf->pos.next; hpo; hpo = hpn) {
  527.         hpn = hpo->next;
  528.         zfree(hpo, sizeof(struct heappos));
  529.     }
  530.     if (hfp)
  531.         hfp->next = hf->next;
  532.     else
  533.         heaps = hf->next;
  534.     zfree(hf->arena, HEAPSIZE);
  535.     zfree(hf, sizeof(struct heap));
  536.  
  537.     for (mp = NULL, m = m_free; m && m->len < size; mp = m, m = m->next);
  538.     }
  539.  
  540.     if (!m) {
  541.     n = (size + M_HSIZE + m_pgsz - 1) & ~(m_pgsz - 1);
  542.  
  543.     if (((char *) (m = (struct m_hdr *) sbrk(n))) == ((char *) -1)) {
  544. #ifdef MEM_WARNING
  545.         zerr("allocation error at sbrk: %e", NULL, 0);
  546. #endif
  547.         return NULL;
  548.     }
  549.  
  550.     if (!m_low)
  551.         m_low = (char *) m;
  552.  
  553. #ifdef MEM_DEBUG
  554.     m_s += n;
  555.  
  556.     if (!m_l)
  557.         m_l = m;
  558. #endif
  559.  
  560.     m_high = ((char *) m) + n;
  561.  
  562.     m->len = n - M_ISIZE;
  563.     m->next = NULL;
  564.  
  565.     if (mp = m_lfree)
  566.         m_lfree->next = m;
  567.     m_lfree = m;
  568.     }
  569.  
  570.     if ((n = m->len - size) > M_MIN) {
  571.     struct m_hdr *mtt = (struct m_hdr *) (((char *) m) + M_ISIZE + size);
  572.  
  573.     mtt->len = n - M_ISIZE;
  574.     mtt->next = m->next;
  575.  
  576.     m->len = size;
  577.  
  578.     if (m_lfree == m)
  579.         m_lfree = mtt;
  580.  
  581.     if (mp)
  582.         mp->next = mtt;
  583.     else
  584.         m_free = mtt;
  585.     }
  586.     else if (mp) {
  587.     if (m == m_lfree)
  588.         m_lfree = mp;
  589.     mp->next = m->next;
  590.     }
  591.     else {
  592.     m_free = m->next;
  593.     if (m == m_lfree)
  594.         m_lfree = m_free;
  595.     }
  596.  
  597.     if (s) {
  598.     struct m_shdr *sh, *shn;
  599.  
  600.     m->free = sh = (struct m_shdr *) (((char *) m) + 
  601.                       sizeof(struct m_hdr) + os);
  602.     m->used = 1;
  603.  
  604.     for (n = M_SNUM - 2; n--; sh = shn)
  605.         shn = sh->next = sh + s;
  606.     sh->next = NULL;
  607.  
  608.     m->next = m_small[s];
  609.     m_small[s] = m;
  610.  
  611. #ifdef MEM_DEBUG
  612.     m_m[os / M_ISIZE]++;
  613. #endif
  614.  
  615.     return (MALLOC_RET_T) (((char *) m) + sizeof(struct m_hdr));
  616.     }
  617.  
  618. #ifdef MEM_DEBUG
  619.     m_m[m->len < (1024 * M_ISIZE) ? (m->len / M_ISIZE) : 1024]++;
  620. #endif
  621.  
  622.     return (MALLOC_RET_T) &m->next;
  623. }
  624.  
  625. void zfree(p, sz)        /**/
  626. vptr p;
  627. int sz;
  628. {
  629.     struct m_hdr *m = (struct m_hdr *) (((char *) p) - M_ISIZE), *mp, *mt;
  630.     int i;
  631.  
  632. #ifdef SECURE_FREE
  633.     sz = 0;
  634. #else
  635.     sz = (sz + M_ALIGN - 1) & ~(M_ALIGN - 1);
  636. #endif
  637.  
  638.     if (!p)
  639.     return;
  640.  
  641.     if (((char *) p) < m_low || ((char *) p) > m_high ||
  642.     ((long) p) & (M_ALIGN - 1)) {
  643.  
  644. #ifdef MEM_WARNING
  645.         zerr("attempt to free storage at invalid address", NULL, 0);
  646. #endif    
  647.  
  648.     return;
  649.     }
  650.  
  651.  fr_rec:
  652.  
  653.     if ((i = sz / M_ISIZE) < M_NSMALL || !sz)
  654.     for (; i < M_NSMALL; i++) {
  655.         for (mp = NULL, mt = m_small[i]; 
  656.          mt && (((char *) mt) > ((char *) p) || 
  657.             (((char *) mt) + mt->len) < ((char *) p));
  658.          mp = mt, mt = mt->next);
  659.  
  660.         if (mt) {
  661.         struct m_shdr *sh = (struct m_shdr *) p, *sh2;
  662.  
  663. #ifdef SECURE_FREE
  664.         if ((((char *) p) - (((char *) mt) + sizeof(struct m_hdr))) %
  665.             M_BSLEN(mt->len)) {
  666.  
  667. #ifdef MEM_WARNING
  668.             zerr("attempt to free storage at invalid address", NULL, 0);
  669. #endif
  670.             return;
  671.         }
  672.  
  673.         for (sh2 = mt->free; sh2; sh2 = sh2->next)
  674.             if (((char *) p) == ((char *) sh2)) {
  675.  
  676. #ifdef MEM_WARNING
  677.             zerr("attempt to free already free storage", NULL, 0);
  678. #endif
  679.             return;
  680.             }
  681. #endif
  682.  
  683.         sh->next = mt->free;
  684.         mt->free = sh;
  685.  
  686. #ifdef MEM_DEBUG
  687.         m_f[M_BSLEN(mt->len) / M_ISIZE]++;
  688. #endif
  689.         
  690.         if (--mt->used) {
  691.             if (mp) {
  692.             mp->next = mt->next;
  693.             mt->next = m_small[i];
  694.             m_small[i] = mt;
  695.             }
  696.             return;
  697.         }
  698.  
  699.         if (mp)
  700.             mp->next = mt->next;
  701.         else
  702.             m_small[i] = mt->next;
  703.  
  704.         m = mt;
  705.         p = (vptr) &m->next;
  706.  
  707.         break;
  708.         }
  709.         else if (sz) {
  710.         sz = 0;
  711.         goto fr_rec;
  712.         }
  713.     }
  714.  
  715. #ifdef MEM_DEBUG
  716.     if (!mt)
  717.     m_f[m->len < (1024 * M_ISIZE) ? (m->len / M_ISIZE) : 1024]++;
  718. #endif
  719.  
  720. #ifdef SECURE_FREE
  721.     for (mt = (struct m_hdr *) m_low; 
  722.      ((char *) mt) < m_high;
  723.      mt = (struct m_hdr *) (((char *) mt) + M_ISIZE + mt->len))
  724.     if (((char *) p) == ((char *) &mt->next))
  725.         break;
  726.  
  727.     if (((char *) mt) >= m_high) {
  728.  
  729. #ifdef MEM_WARNING
  730.     zerr("attempt to free storage at invalid address", NULL, 0);
  731. #endif
  732.     return;
  733.     }
  734. #endif
  735.  
  736.     for (mp = NULL, mt = m_free; mt && mt < m; mp = mt, mt = mt->next);
  737.  
  738.     if (m == mt) {
  739.  
  740. #ifdef MEM_WARNING
  741.     zerr("attempt to free already free storage", NULL, 0);
  742. #endif
  743.     return;
  744.     }
  745.  
  746.     if (mt && ((char *) mt) == (((char *) m) + M_ISIZE + m->len)) {
  747.     m->len += mt->len + M_ISIZE;
  748.     m->next = mt->next;
  749.     
  750.     if (mt == m_lfree)
  751.         m_lfree = m;
  752.     }
  753.     else
  754.     m->next = mt;
  755.  
  756.     if (mp && ((char *) m) == (((char *) mp) + M_ISIZE + mp->len)) {
  757.     mp->len += m->len + M_ISIZE;
  758.     mp->next = m->next;
  759.  
  760.     if (m == m_lfree)
  761.         m_lfree = mp;
  762.     }
  763.     else if(mp)
  764.     mp->next = m;
  765.     else
  766.     m_free = m;
  767.  
  768.     if ((((char *) m_lfree) + M_ISIZE + m_lfree->len) == m_high &&
  769.     m_lfree->len >= m_pgsz + M_MIN) {
  770.     long n = (m_lfree->len - M_MIN) & ~(m_pgsz - 1);
  771.  
  772.     m_lfree->len -= n;
  773.     if (brk(m_high -= n) == -1) {
  774. #ifdef MEM_WARNING
  775.         zerr("allocation error at brk: %e", NULL, 0);
  776. #endif
  777.     }
  778.  
  779. #ifdef MEM_DEBUG
  780.     m_b += n;
  781. #endif
  782.     }
  783. }
  784.  
  785. FREE_RET_T free(p)
  786. FREE_ARG_T p;
  787. {
  788.     zfree(p, 0);
  789.  
  790. #ifdef FREE_DO_RET
  791.     return 0;
  792. #endif    
  793. }
  794.  
  795. void zsfree(p)        /**/
  796. char *p;
  797. {
  798.     if (p)
  799.     zfree(p, strlen(p) + 1);
  800. }
  801.  
  802. MALLOC_RET_T realloc(p, size)
  803. MALLOC_RET_T p;
  804. MALLOC_ARG_T size;
  805. {
  806.     struct m_hdr *m = (struct m_hdr *) (((char *) p) - M_ISIZE), *mp, *mt;
  807.     char *r;
  808.     int i, l = 0;
  809.  
  810.     if (!p && size)
  811.     return (MALLOC_RET_T) malloc(size);
  812.     if (!p || !size)
  813.     return (MALLOC_RET_T) p;
  814.  
  815.     for (i = 0; i < M_NSMALL; i++) {
  816.     for (mp = NULL, mt = m_small[i]; 
  817.          mt && (((char *) mt) > ((char *) p) || 
  818.             (((char *) mt) + mt->len) < ((char *) p));
  819.          mp = mt, mt = mt->next);
  820.  
  821.     if (mt) {
  822.         l = M_BSLEN(mt->len);
  823.         break;
  824.     }
  825.     }
  826.     if (!l)
  827.     l = m->len;
  828.  
  829.     r = malloc(size);
  830.     memcpy(r, (char *) p, (size > l) ? l : size);
  831.     free(p);
  832.  
  833.     return (MALLOC_RET_T) r;
  834. }
  835.  
  836.  
  837. MALLOC_RET_T calloc(n, size)
  838. MALLOC_ARG_T n;
  839. MALLOC_ARG_T size;
  840. {
  841.     long l;
  842.     char *r;
  843.  
  844.     if(!(l = n * size))
  845.     return (MALLOC_RET_T) m_high;
  846.  
  847.     r = malloc(l);
  848.  
  849.     memset(r, 0, l);
  850.  
  851.     return (MALLOC_RET_T) r;
  852. }
  853.  
  854.  
  855. FREE_RET_T cfree(p)
  856. FREE_ARG_T p;
  857. {
  858.     free(p);
  859.  
  860. #ifdef FREE_DO_RET
  861.     return 0;
  862. #endif
  863. }
  864.  
  865.  
  866. #ifdef MEM_DEBUG
  867.  
  868. int bin_mem(name, argv, ops, func)            /**/
  869. char *name;
  870. char **argv;
  871. char *ops;
  872. int func;
  873. {
  874.     int i, ii, fi, ui, j;
  875.     struct m_hdr *m, *mf, *ms;
  876.     char *b, *c, buf[40];
  877.     long u = 0, f = 0;
  878.     Lknode nd;
  879.  
  880.     if (ops['v']) {
  881.     printf("The lower and the upper addresses of the heap. Diff gives\n");
  882.     printf("the difference between them, i.e. the size of the heap.\n\n");
  883.     }
  884.  
  885.     printf("low mem %ld\t high mem %ld\t diff %ld\n", 
  886.        (long) m_l, (long) m_high, (long) (m_high - ((char *) m_l)));
  887.  
  888.     if (ops['v']) {
  889.     printf("\nThe number of bytes that were allocated using sbrk() and\n");
  890.     printf("the number of bytes that were given back to the system\n");
  891.     printf("via brk().\n");
  892.     }
  893.  
  894.     printf("\nsbrk %d\tbrk %d\n", m_s, m_b);
  895.  
  896.     if (ops['v']) {
  897.     printf("\nInformation about the sizes that were allocated or freed.\n");
  898.     printf("For each size that were used the number of mallocs and\n");
  899.     printf("frees is shown. Diff gives the difference between these\n");
  900.     printf("values, i.e. the number of blocks of that size that is\n");
  901.     printf("currently allocated. Total is the product of size and diff,\n");
  902.     printf("i.e. the number of bytes that are allocated for blocks of\n");
  903.     printf("this size.\n");
  904.     }
  905.  
  906.     printf("\nsize\tmalloc\tfree\tdiff\ttotal\n");
  907.     for (i = 0; i < 1024; i++)
  908.     if (m_m[i] || m_f[i])
  909.         printf("%d\t%d\t%d\t%d\t%d\n", i * M_ISIZE, m_m[i], m_f[i], 
  910.            m_m[i] - m_f[i], i * M_ISIZE * (m_m[i] - m_f[i]));
  911.  
  912.     if (m_m[i] || m_f[i])
  913.     printf("big\t%d\t%d\t%d\n", m_m[i], m_f[i], m_m[i] - m_f[i]);
  914.  
  915.     if (ops['v']) {
  916.     printf("\nThe list of memory blocks. For each block the following\n");
  917.     printf("information is shown:\n\n");
  918.     printf("num\tthe number of this block\n");
  919.     printf("tnum\tlike num but counted separatedly for used and free\n");
  920.     printf("\tblocks\n");
  921.     printf("addr\tthe address of this block\n");
  922.     printf("len\tthe length of the block\n");
  923.     printf("state\tthe state of this block, this can be:\n");
  924.     printf("\t  used\tthis block is used for one big block\n");
  925.     printf("\t  free\tthis block is free\n");
  926.     printf("\t  small\tthis block is used for an array of small blocks\n");
  927.     printf("cum\tthe accumulated sizes of the blocks, counted\n");
  928.     printf("\tseparatedly for used and free blocks\n");
  929.     printf("\nFor blocks holding small blocks the number of free\n");
  930.     printf("blocks, the number of used blocks and the size of the\n");
  931.     printf("blocks is shown. For otherwise used blocks the first few\n");
  932.     printf("bytes are shown as an ASCII dump.\n");
  933.     }
  934.  
  935.     printf("\nblock list:\nnum\ttnum\taddr\tlen\tstate\tcum\n");
  936.     for (m = m_l, mf = m_free, ii = fi = ui = 1; ((char *) m) < m_high; 
  937.      m = (struct m_hdr *) (((char *) m) + M_ISIZE + m->len), ii++) {
  938.     for (j = 0, ms = NULL; j < M_NSMALL && !ms; j++)
  939.         for (ms = m_small[j]; ms; ms = ms->next)
  940.         if (ms == m)
  941.             break;
  942.  
  943.     if (m == mf)
  944.         buf[0] = '\0';
  945.     else if (m == ms)
  946.         sprintf(buf, "%d %d %d", M_SNUM - ms->used, ms->used,
  947.             (m->len - sizeof(struct m_hdr)) / M_SNUM + 1);
  948.     else {
  949.         for (i = 0, b = buf, c = (char *) &m->next; i < 20 && i < m->len;
  950.          i++, c++)
  951.         *b++ = (*c >= ' ' && *c < 127) ? *c : '.';
  952.         *b = '\0';
  953.     }
  954.  
  955.     printf("%d\t%d\t%ld\t%ld\t%s\t%ld\t%s\n", ii, 
  956.            (m == mf) ? fi++ : ui++,
  957.            (long) m, m->len,
  958.            (m == mf) ? "free" : ((m == ms) ? "small" : "used"),
  959.            (m == mf) ? (f += m->len) : (u += m->len),
  960.            buf);
  961.  
  962.     if (m == mf)
  963.         mf = mf->next;
  964.     }
  965.  
  966.     if (ops['v']) {
  967.     printf("\nHere is some information about the small blocks used.\n");
  968.     printf("For each size the arrays with the number of free and the\n");
  969.     printf("number of used blocks are shown.\n");
  970.     }
  971.  
  972.     printf("\nsmall blocks:\nsize\tblocks (free/used)\n");
  973.  
  974.     for (i = 0; i < M_NSMALL; i++)
  975.     if (m_small[i]) {
  976.         printf ("%d\t", i*M_ISIZE);
  977.         
  978.         for (ii = 0, m = m_small[i]; m; m = m->next) {
  979.         printf("(%d/%d) ", M_SNUM - m->used, m->used);
  980.         if (!((++ii) & 7))
  981.             printf("\n\t");
  982.         }
  983.         putchar('\n');
  984.     }
  985.  
  986.     if (ops['v']) {
  987.     printf("\n\nBelow is some information about the allocation\n");
  988.     printf("behaviour of the zsh heaps. First the number of times\n");
  989.     printf("pushheap(), popheap(), and freeheap() were called.\n");
  990.     }
  991.  
  992.     printf("\nzsh heaps:\n\n");
  993.  
  994.     printf("push %d\tpop %d\tfree %d\n\n", h_push, h_pop, h_free);
  995.  
  996.     if (ops['v']) {
  997.     printf("\nThe next list shows for several sizes the number of times\n");
  998.     printf("memory of this size were taken from heaps.\n\n");
  999.     }
  1000.  
  1001.     printf("size\tmalloc\ttotal\n");
  1002.     for (i = 0; i < 1024; i++)
  1003.     if (h_m[i])
  1004.         printf("%d\t%d\t%d\n", i * H_ISIZE, h_m[i], i * H_ISIZE * h_m[i]);
  1005.     if (h_m[1024])
  1006.     printf("big\t%d\n", h_m[1024]);
  1007.  
  1008.     return 0;
  1009. }
  1010.  
  1011. #endif
  1012.  
  1013. #else /* not USE_ZSH_MALLOC */
  1014.  
  1015. void zfree(p, sz)        /**/
  1016. vptr p;
  1017. int sz;
  1018. {
  1019.     if (p)
  1020.     free(p);
  1021. }
  1022.  
  1023. void zsfree(p)            /**/
  1024. char *p;
  1025. {
  1026.     if (p)
  1027.     free(p);
  1028. }
  1029.  
  1030. #endif
  1031.